Remove 9

Time: O(LogN); Space: O(1); hard

Start from integer 1, remove any integer that contains 9 such as 9, 19, 29… So now, you will have a new integer sequence: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, …

Given a positive integer N, you need to return the N-th integer after removing. Note that 1 will be the first integer.

Example 1:

Input: 9

Output: 10

Hint:

  1. N will not exceed 9 x 10^8.

[1]:

class Solution1(object):
    def newInteger(self, n) -> int:
        """
        :type n: int
        :rtype: int
        """
        result, base = 0, 1
        while n > 0:
            result += (n % 9) * base
            n //= 9
            base *= 10
        return result

[2]:

s = Solution1()
n = 9
assert s.newInteger(n) == 10